home *** CD-ROM | disk | FTP | other *** search
/ Amiga Format CD 40 / Amiga Format CD40 (1999-05-11)(Future Publishing)(GB)(Track 1 of 3)[!][issue 1999-06].iso / -readerstuff- / paul_qureshi / info / spline.txt < prev    next >
Text File  |  1999-03-27  |  7KB  |  206 lines
  1.  
  2.                ---------------------
  3.             Little Spline Guide
  4.                ---------------------
  5.  
  6. Written by
  7.         Jani "Flame / Pygmy Projects" Vaarala
  8.             Amiga ftpadministrator of x2ftp.oulu.fi
  9.  
  10. Formulas from
  11.         December 1986 BYTE article "FREE-FORM CURVES ON YOUR MICRO"
  12.         by Steve Enns (starting from page 225)
  13.  
  14. Spreading
  15.         Freely spread. But! Making money out of this is not allowed!
  16.         New versions (if needed) will be at FTP-site x2ftp.oulu.fi
  17.  
  18. Corrections
  19.         25.1.1995 --- in example t=0 --> 1.0 ..
  20.          2.3.1995 --- some errors in matrix forms corrected.
  21.  
  22. My intention is NOT to give ANY mathematical background of splines, but just
  23. to give the formulas and give some ideas for fast and easy (haha 8) spline use.
  24.  
  25. FORMULAS
  26. --------
  27.  
  28.     Bezier Form
  29.     -----------
  30.  
  31.     Developed by Pierre Bézier.
  32.  
  33.     1° Matrix form
  34.  
  35.                        / P1 \
  36.         C(t) = [t³ t² t 1] B  |  P2  |
  37.                       |  P3  |
  38.                        \ P4 /
  39.  
  40.        where B is
  41.  
  42.          / -1  3 -3  1 \
  43.     B = |   3 -6  3  0  |
  44.         |  -3  3  0  0  |
  45.          \  1  0  0  0 /
  46.  
  47.  
  48.        P1, P2, P3 and P4 are spline control points (points which guide
  49.        the curve) (see example 1).
  50.  
  51.        And t is "spline-scale" which varies from 0.0 to 1.0.
  52.        When t is 0.0, the curve is on point P1. As t approaches
  53.        1.0 the curve approaches point P4 (passing points P2 and P3).
  54.        When t reaches 1.0 the curve is on point P4.
  55.  
  56.     2° Equation form
  57.  
  58.         C(t) = (  -t³ + 3*t² - 3*t + 1) * P1 +
  59.                ( 3*t³ - 6*t² + 3*t    ) * P2 +
  60.                (-3*t³ + 3*t²          ) * P3 +
  61.                (   t³                 ) * P4
  62.     
  63.        Note that C(t) gives only one coordinate. If you want to use
  64.        2D-splines then you must first calculate C(t) with P1-P4 values being
  65.        x-coordinates, and then calculate C(t) with P1-P4 values being
  66.        y-coordinates. For 3D-splines you must calculate C(t) three times etc.
  67.  
  68. Example 1: (2D-bezier)
  69. ----------
  70.  
  71. Control points (x-spline point, y-spline point)
  72.  
  73.     (100,100) (150,50) (200,150) (250,100)
  74.  
  75.     should give sine-like curve (see SINE) starting from coordinate
  76.     (100,100) and ending at (250,100).
  77.  
  78.  
  79.  
  80.     B-Spline form
  81.     -------------
  82.  
  83.     Matrix form
  84.  
  85.                        / P(i-1) \
  86.         C(t) = [t³ t² t 1] B  |  P(i)    |
  87.                       |  P(i+1)  |
  88.                        \ P(i+2) /
  89.  
  90.        where B is
  91.  
  92.          / -1  3 -3  1 \
  93.     B = |   3 -6  3  0  |
  94.         |  -3  0  3  0  |
  95.          \  1  4  1  0 /
  96.  
  97.     2° Equation form
  98.  
  99.         C(t) = (-1/6*t³ + 1/2*t² - 1/2*t + 1/6) * P(i-1) +
  100.                ( 1/2*t³ -     t²         + 2/3) * P(i)   +
  101.                (-1/2*t³ + 1/2*t² + 1/2*t + 1/6) * P(i+1) +
  102.                ( 1/6*t³                       ) * P(i+2)
  103.  
  104.  
  105.     where P(i) is "current point" (point around the curve is being
  106.     calculated. If N is the amount of control points, then
  107.     i goes from 2 to n-2, and for every i t varies from 0.0 to 1.0.
  108.     B-Spline curve begins from P(2) but P(1) (point before) has effect
  109.     on the curve. As you can see from the formula, only four points
  110.     affect our curve around one control point.
  111.  
  112.     As you see this B-Spline form allows user to have as many control
  113.     points as desired. Bézier curves can also be utilized this way,
  114.     but because B-Spline follows control points more closely I have
  115.     chosen the B-Spline in my productions.
  116.  
  117.  
  118.     Basic spline(draw) loop should be like:
  119.  
  120.         n = amount of spline controlpoints
  121.         s = step (how many values / control point)
  122.  
  123.         for ( i = 2 --> n-2 )
  124.  
  125.           for ( t=0.0 --> 1.0 step s)
  126.  
  127.             x = C(t) With x-control points
  128.             y = C(t) With y-control points
  129.             ....
  130.  
  131.             setpoint(x,y, ....)
  132.  
  133.  
  134. CONNECTING SPLINE(S)
  135. --------------------
  136.  
  137. To make the spline connected (end goes to beginning) you should copy the
  138. first 3 control points ( P(0), P(1) and P(2) ) to end of the control points.
  139. (This was a feature in my spline editor, thanks to Silver Eagle for the idea)
  140.  
  141. If you want to connect 2 or more splines together then you should make
  142. the first 3 points in 2nd spline the same as in 1st spline etc etc ...
  143.  
  144. USAGE
  145. -----
  146.  
  147. As you can see there are 4 t³-operations, 3 t²-operations and 4 multiplications
  148. with control points. That gives total of
  149.  
  150. 4*2 + 3 + 4 = 15 multiplications. That makes 30 for one 2D-point which is too
  151. much for practical use. Coders with some experience should see that
  152. [t³ t² t 1] * B (the coefficients of control points) can be pretabled to
  153. reduce the amount of multiplications to only 4 / control point. So for
  154. 2D-point this would be 8 multiplications (not so bad).
  155.  
  156. In Extension (1st in Assembly'93 amiga demo competition) the movements
  157. (in Shapecity and Dotcity) were done using my spline-routine, which had
  158. 1024 byte table for coefficients (that is 256 coeffs/control point).
  159.  
  160. My "Morpher" routine used splines to create smooth morph. The morphing is done
  161. very easily. I made a spline-editor and we calculated some nice looking (filled)
  162. spline-figures. To make it morph I made linear (mistake!) slide from
  163. one spline control point set to another. Because of the lack
  164. of time I didn't have time to make the the morph use non-linear (S-curve)
  165. slide (that is why the morph isn't that smooth as it could be).
  166.  
  167. SINE (maybe some other curves too ?)
  168. ------------------------------------
  169.  
  170. My littlebrother (Sami "Silver Eagle / Pygmy Projects" Vaarala) has used
  171. succesfully splines to create approximation of sine. In G-Force
  172. (Assembly'94 amiga 40k introcompo winner) Sami used 11 spline controlpoints
  173. to make the sine (45 degrees of it) and some values for scaling the sine.
  174. In G-Force the sine calculation code was around 20 instructions and data for
  175. the sine was around 15 16-bit words. And it calculated 40k of sinetable in
  176. around 20 frames (2/5 second) which had 16-bit sine values (32767 -> -32768)
  177. and had average error on sine values less than 1! (For example, If the real
  178. value would be 4123 then the value (from approximation) would be 4122 or 4124.)
  179. (All this work was done, because he needed large sinetables and math-libraries
  180.  couldn't be used (competition rules))
  181.  
  182.  
  183. If you have any suggestions/flames:
  184.  
  185.  
  186.         (snail mail)
  187.  
  188.         Jani Vaarala
  189.         Tellervontie 2 A 15
  190.         90570 Oulu
  191.         Finland
  192.  
  193.         (email)
  194.  
  195.         flame@stekt.oulu.fi (questions/suggestions about this text or
  196.                      something. Please dont fill my mailbox
  197.                      with zillion questions about usual
  198.                      coding stuff (because you can ask your
  199.                      questions in comp.amiga.programmer)
  200.  
  201.         ftpadm@x2ftp.oulu.fi (questions about the programming site
  202.                       x2ftp.oulu.fi)
  203.  
  204.  
  205. Special thank to    Harri Kinnunen for pointing me out the article (BYTE'86).
  206.